package demo;
import java.util.*;
/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-07-06
 * Time: 9:20
 */
class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        //优先级队列
        //使用map统计单词的次数
        Map<String, Integer> map = new HashMap<>();
        for (String str : words) {
            map.put(str, map.getOrDefault(str, 0) + 1);
        }
        //去前k个高频单词那就建立小根堆
        PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue(new Comparator<Map.Entry<String, Integer>>() {
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                return o1.getValue().compareTo(o2.getValue()) == 0 ? o1.getKey().compareTo(o2.getKey())
                        : o1.getValue().compareTo(o2.getValue());
            }
        });

        for (Map.Entry<String, Integer> entry : pq) {
            pq.offer(entry);
            if (pq.size() > k) {
                pq.poll();
            }
        }
        List<String> list = new ArrayList<>();
        for (Map.Entry<String, Integer> entry : pq) {
            list.add(pq.poll().getKey());
        }
        Collections.reverse(list);
        return list;
    }
}
public class TestDemo {

    public static void main(String[] args) {
       String[] words = {"i", "love", "leetcode", "i", "love", "coding"};
       Solution solution = new Solution();
       solution.topKFrequent(words,2);


    }


}
